package org.usmile.algorithms.leetcode.hard;

/**
 * 233. 数字 1 的个数
 *
 * 给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
 *
 * 示例 1：
 * 输入：n = 13
 * 输出：6
 *
 *  示例 2：
 * 输入：n = 0
 * 输出：0
 *
 * 提示：
 * 0 <= n <= 109
 */
public class _0233 {
}

class _0233_Solution {
    public int countDigitOne(int n) {
        int count = 0;
        for (long i = 1; i <= n; i *= 10) {
            long divider = i * 10;
            count += (n / divider) * i + Math.min(Math.max(n % divider - i + 1, 0L), i);
        }

        return count;
    }
}

class _0233_Solution1 {
    public int countDigitOne(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            int x = i;
            while (x != 0) {
                if (x % 10 == 1) {
                    count++;
                }

                x = x / 10;
            }
        }

        return count;
    }
}